package ds.array;

/**
 * 基于二分查找的有序数组
 * 
 * 查找快 O(log2(N))
 * 
 * 插入、删除慢 O(N)
 **/
public class OrdArray {

	private long[] a;    // ref to array a
	private int nElems;
	// --------------------------------
	public OrdArray(int max)      // constructor
	{
		a = new long[max];
		nElems = 0;
	}
	
	//二分查找
	public int find(long searchKey)
	{
		if(nElems == 0)
			return -1;
		int lowerBound = 0;
		int upperBound = nElems - 1;
		if(a[lowerBound]>searchKey || a[upperBound]<searchKey)
			return -1;
		
		int p = (lowerBound + upperBound) / 2;
		
		while(p!=lowerBound && p!=upperBound)
		{
			if(a[p]==searchKey)
				return p;
			if(a[p]<searchKey)
				lowerBound = p;
			if(a[p]>searchKey)
				upperBound = p;
			
			p = (lowerBound + upperBound) / 2;
		}
		
		if(a[lowerBound] == searchKey)
			return lowerBound;
		if(a[upperBound] == searchKey)
			return upperBound;
		return -1;
	}
	
	/**递归二分查找，不推荐- -*/
	public int recFind(long searchKey) {
		if(nElems == 0)
			return -1;
		int lowerBound = 0;
		int upperBound = nElems - 1;
		if(a[lowerBound]>searchKey || a[upperBound]<searchKey)
			return -1;
		
		return recFind(searchKey, lowerBound, upperBound);
	}
	
	private int recFind(long searchKey, int lowerBound, int upperBound)
	{
		if(lowerBound > upperBound)
			return -1;
		
		int p = ( lowerBound + upperBound ) / 2;
			
		if (a[p] == searchKey)
			return p;
		else if (a[p] < searchKey)
			return recFind(searchKey, p+1, upperBound);
		else
			return recFind(searchKey, lowerBound, p-1);
	}
	
	//排序insert
	public void insert(long value)
	{
		if(nElems == a.length)
			System.out.println("数组已满，插入无效");
		
		int j;
		for(j=0;j<nElems;j++)
			if(value < a[j]) break;
		
		//if(j!=nElems)
		//{
		for(int k=nElems-1;k>=j;k--)
		{
			a[k+1] = a[k];
		}
		a[j] = value; //a[k+1] = value;
		nElems ++;
		return;
		//}
		
		//a[nElems] = value;
		//nElems++;
	}
	
	public boolean contains(long value)
	{
		return find(value)!=-1;
	}
	
	public void display() // displays array contents
	{
		for(int j=0;j<nElems;j++) // for each element
		{
			System.out.print(a[j] + " "); // display it
		}
		System.out.println("");
	}
	
	public boolean delete(long value)
	{
		int j;
		if((j=find(value))!=-1)
		{
			for(int k=j;k<nElems-1;k++)
				a[k]=a[k+1];
			nElems--;
			return true;
		}
		else
			return false;
	} // end delete()
	
}

class OrdArrayAPP
{
	public static void main(String[] args) {

		OrdArray a = new OrdArray(1000);
		a.insert(10);
		a.insert(5);
		a.insert(2);
		a.insert(3);
		a.insert(92);
		a.insert(34);
		a.insert(55);
		
		a.display();
		
		a.delete(5);
		a.delete(55);
		a.display();
		
		a.recFind(92);
		
		System.out.println(a.contains(55));
		System.out.println(a.contains(92));
		System.out.println((a.find(92)));
		System.out.println((a.recFind(91)));
	}
}
